<?php
/** 
* @file NTree.class.php
* @author kenlixin@gmail.com
* @version 0.1 design
* @date 2009-11-23
*/

class NTree{
    
    /** 
    * @db and other setting: must be use ThinkPHP Model Class or adapter.
    * @param 'db'
    * @param 'table'
    * @param 'key'
    * @param 'left'
    * @param 'right'
    */
    public $_setting = array(
        '_db'        =>  'localhost',
        '_user'      =>  'root',
        '_password'  =>  '',
        '_table'     =>  'nested_category',
        '_key'       =>  'id',
        '_left'      =>  'lft',
        '_right'     =>  'rgt',
        '_title'      =>  'title',   
    );
    
    public function __construct($setting = null){
      if( isset($setting) && is_array($setting) ){           
          foreach($setting as $key=>$item){
              if(array_key_exists('_'.$key, $this->_setting)){
                $this->_setting['_'.$key] = $item;
              }
          }
      }
    }
    
    public function insertRootNode($node){
      extract($this->_setting);

      $node[$_left] =1;
      $node[$_right]=2;

      KenDon::load('KDHelper');
      $outArray = KDHelper::arraySqlFormat(array($node));
      //var_dump($outArray);

      
      $insertFields = implode(',', array_keys($outArray['output'][0]) );
      $insertValues = implode(',', array_values( $outArray['output'][0] ) );
      
      $sqlInsert = "INSERT INTO `$_table` ($insertFields) VALUES($insertValues);";
      //var_dump($sqlInsert);
      
      //*
      $model = new KDModel();
      try{
          $model->startTrans();
          $model->execute($sqlUpdateLeft);
          $model->execute($sqlUpdateRight);
          $model->execute($sqlInsert);
          $model->commit();
          return true;
      }catch(Exception $e){   
          throw $e;
          return false;
      }
      //*/
    }
    
    public function init(){
      extract($this->_setting);
      return $this->insertRootNode(array($_title=>'#virtual_root#'));
    }

    public function isNode($node){
        extract($this->_setting);
        if( is_array($node) && isset($node[$_key]) && isset($node[$_left]) &&  isset($node[$_right]) ){
            return true;
        }else{
            return false;
        }
    }
    
    public function getNode($key){

        extract($this->_setting);

        $sql    =   "SELECT * FROM `$_table` WHERE `$_key` = $key;";
        $m      =   new KDModel();
        $record =   $m->query($sql);
        $result =   count($record)>0 ? $record[0]:null;

        return $result;
    } 
    
    public function getRootNode(){
        extract($this->_setting);
        
        $sql        =   "SELECT * FROM `$_table` WHERE  `$_right` = (SELECT MAX(`$_right`) FROM `$_table`);";
        $model      =   new KDModel();
        $record     =   $model->query($sql);
        $result     =   count($record)>0? $record[0]:null;
        
        return $result;
    }
    
    public function getRootNodes(){
      extract($this->_setting);
      return $this->getICNodes( $this->getRootNode());
    }
    
    public function getParentNode($node){
        if($this->isNode($node) == false){return null;}

        extract($this->_setting);
        $node_lft   =   $node[$_left];
        $node_rgt   =   $node[$_right];

        $sql        =  "SELECT * FROM `$_table` WHERE `$_right`=(SELECT MIN(`$_right`) FROM `{$_table}` WHERE `$_left`<$node_lft AND `$_right`>$node_rgt ) ORDER BY {$_left} ASC; ";
        //dump($sql);
        
        $model      =   new KDModel();
        $record     =   $model->query($sql);
        $result     =   count($record)>0? $record[0] : null;

        return $result;
    }
    
    public function getNodePath($node){
        
        if($this->isNode($node) == false){return null;}

        extract($this->_setting);

        $node_lft   =   $node[$_left];
        $node_rgt   =   $node[$_right];

        $sql        =   "SELECT * FROM `$_table` WHERE `$_left`<$node_lft AND `$_right`>$node_rgt;";
        //echo $sql;

        $model      =   new KDModel();
        $record     =   $model->query($sql);
        $result     =   count($record)>0 ? $record : null;

        return $result;    
    }

    public function getAllNodes(){
        extract($this->_setting);

        $sql        =   "SELECT * FROM `$_table` ORDER BY `$_left` ASC;";

        $model      =   new KDModel();
        $record     =   $model->query($sql);
        $result     =   count($record)>0 ? $record : null;

        return $result;
    }  
    
    public function getSubNodes($node, $offset=0, $rows=5000){
        
        if($this->isNode($node) == false){return null;}

        extract($this->_setting);
         
        $node_lft   =   $node[$_left];
        $node_rgt   =   $node[$_right];

        $sql        =   "SELECT * FROM `$_table` WHERE `$_left` BETWEEN $node_lft AND $node_rgt ORDER BY `$_left` ASC LIMIT $offset, $rows;";
        
        $model      =   new KDModel();
        $record     =   $model->query($sql);
        $result     =   count($record)>0 ? $record : null;
        
        return $result; 
    } 
    
    /** 第一子节点
    * 
    */
    public function getFCNode($node){
      
      if($this->isNode($node) == false){return null;}
      
      extract($this->_setting);
      
      $record = self::getSubNodes($node,0,2);
      $result = count($record)>1 ? $record[1] : null;
      
      return $result;
    }
    
    /** 同父同层节点 same level nodes
    *
    */
    public function getSLNodes($node){
        
        if($this->isNode($node) == false){return null;}
        
        extract($this->_setting);

        $parentNode = $this->getParentNode($node);
        
        if($this->isNode($parentNode) == false ){return $node;}
        //var_dump($parentNode);
        
        $subNodes = $this->getSubNodes($parentNode); 
        array_shift($subNodes);
        //var_dump($subNodes);
        
        $stack = $subNodes[0][$_right];
        //var_dump($stack);
        $result = array(
          //$subNodes[0],
        );
        foreach($subNodes as $item){
            if($item[$_right]>=$stack){
                $stack=$item[$_right];
                $result[]=$item;
            }
        }
        return $result;
    }
    
    /** 直接子节点 ImmediateChildNodes
    *
    */
    public function getICNodes($node){
      $fnode = self::getFCNode($node);
      //var_dump($fnode);
      $record = self::getSLNodes($fnode);
      //var_dump($record);
      $result = count($record)>0 ? $record : null;
      return $result;
    }
    
    public function displaySubTree($node){
        if($this->isNode($node == false)){return null;}

        extract($this->_setting);

        $result = array();
        $stack = array();

        $nodes = $this->getSubNodes($node); 
        
        foreach($nodes as $row){
            if(count($stack)>0){
                while($stack[count($stack)-1] < $row[$_right]){
                    array_pop($stack);
                }
            }
            $result[] = str_repeat('--', count($stack)) . $row[$_title];
            $stack[]    =   $row[$_right];
        }
        
        return $result;
    }
    
    public function displayTree(){
        return $this->displaySubTree($this->getRootNode()); 
    }
    
    public function getChildCount($node){
        extract($this->_setting);
        return ( $node[$_right] - $node[$_left] - 1 )/2;
    }

    /** 
    * @brief insertNode class, default position is 'after'.
    * 
    * @param $targetNode
    * @param $referNode
    * @param $position after|before|below.
    * @return  true|false
    */
    public function insertNode($targetNode, $referNode, $position='after'){
        
        if($this->isNode($referNode) == false){ return false; }
        
        if($position !== 'after' && $position !== 'before' && $position !== 'below'){
          return false;
        }
        
        extract($this->_setting);
        
        if($position == 'after'){
          $updateLocalRefer = $referNode[$_right];
          $insertRefer = $referNode[$_right];
          
          //所有left>$referParentNode[right]的节点,left=left+2
          $sqlUpdateLeft  = "UPDATE `$_table` SET `$_left`=`$_left`+2 WHERE `$_left`>$updateLocalRefer;";
          
          //所有right>$referParentNode[right]的节点,right+right+2
          $sqlUpdateRight = "UPDATE `$_table` SET `$_right`=`$_right`+2 WHERE `$_right`>$updateLocalRefer;";
        }
        
        if($position == 'before'){
        
            $updateLocalRefer = $referNode[$_left]-1;
            
            $insertRefer = $updateLocalRefer;
            
            $sqlUpdateLeft = "UPDATE `$_table` SET `$_left`=`$_left`+2 WHERE `$_left`>$updateLocalRefer;";
            
            $sqlUpdateRight = "UPDATE `$_table` SET `$_right`=`$_right`+2 WHERE `$_right`>$updateLocalRefer;";
        }
        
        if($position == 'below'){
             
            $updateLocalRefer = $referNode[$_right]-1;
            
            $insertRefer = $updateLocalRefer;
            
            $sqlUpdateLeft      =   "UPDATE `$_table` SET `$_left`=`$_left`+2 WHERE `$_left`>$updateLocalRefer;";
            
            $sqlUpdateRight     =   "UPDATE `$_table` SET `$_right`=`$_right`+2 WHERE `$_right`>$updateLocalRefer;";

        }
        
        echo $sqlUpdateLeft;
        echo $sqlUpdateRight;
        
        //排除$targetNode[$_key]
        //if( array_key_exists($targetNode[$_key]) ){
        //  unset($targetNode[$_key]);
        //}
        
        //生成左右值
        $targetNode[$_left] = $insertRefer+1;
        $targetNode[$_right] = $insertRefer+2;
        
        //生成插入节点SQL
        KenDon::load('KDHelper');
        $outArray = KDHelper::arraySqlFormat(array($targetNode));
        //var_dump($outArray);

        $insertFields = implode(',', array_keys($outArray['output'][0]) );
        $insertValues = implode(',', array_values( $outArray['output'][0] ) );
        
        $sqlInsert = "INSERT INTO `$_table` ($insertFields) VALUES($insertValues);";
        echo $sqlInsert;
        
        //*
        $model = new KDModel();
        try{
            $model->startTrans();
            $model->execute($sqlUpdateLeft);
            $model->execute($sqlUpdateRight);
            $model->execute($sqlInsert);
            $model->commit();
            return true;
        }catch(Exception $e){   
            throw $e;
            return false;
        }
        //*/
    }

    public function deleteNode($node){
    
      if($this->isNode($node) == false){ return false; }
      
      extract($this->_setting);

      $nodeLeft       =   $node[$_left];
      $nodeRight      =   $node[$_right];
      $width          =   $nodeRight - $nodeLeft +1;

      $sqlDelete              = "DELETE FROM `$_table` WHERE `$_left` BETWEEN $nodeLeft AND $nodeRight;";
      dump($sqlDelete);
      
      $sqlUpdateLeftValues    = "UPDATE `$_table` SET `$_right`=`$_right`-$width WHERE `$_right`>$nodeRight;";
      dump($sqlUpdateLeftValues);
      
      $sqlUpdateRightValues   = "UPDATE `$_table` SET `$_left`=`$_left`-$width WHERE `$_left`>$nodeRight;";
      dump($sqlUpdateRightValues); 

      //*
      $model = new KDModel();

      try{
          $model->startTrans();
          $model->execute($sqlDelete);
          $model->execute($sqlUpdateLeftValues);
          $model->execute($sqlUpdateRightValues);
          $model->commit();
          return true;
      }catch(Exception $e){
          throw $e;
          return false;
      }
      //*/
    }
    
    public function deleteAllNode(){
      extract($this->_setting);
      $sql ="DELETE FROM `$_table`;";
      $model = new KDModel();

      try{
          $model->execute($sql);
          return true;
      }catch(Exception $e){
          throw $e;
          return false;
      }
    }

    /** 
    * @brief 
    * 
    * @param $targetNode
    * @param $referNode
    * @param $position after|before|below
    * @return true|false. 
    */
    public function moveNode($targetNode, $referNode, $position='after'){

    }

}
